//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 
//
// 有效字符串需满足： 
//
// 
// 左括号必须用相同类型的右括号闭合。 
// 左括号必须以正确的顺序闭合。 
// 每个右括号都有一个对应的相同类型的左括号。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "()"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s = "()[]{}"
//输出：true
// 
//
// 示例 3： 
//
// 
//输入：s = "(]"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 10⁴ 
// s 仅由括号 '()[]{}' 组成 
// 
//
// Related Topics 栈 字符串 👍 4145 👎 0


package LeetCode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author ldltd
 * @date 2023-09-08 11:12:12
 * @description 20.有效的括号
 */
public class ValidParentheses{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new ValidParentheses().new Solution();
		 System.out.println(solution.isValid("{[]}"));
//		 Deque<Character> stack=new LinkedList<>();
//		 stack.push('a');
//		 stack.push('b');
//		 stack.push('c');
//		 stack.push('d');
//		 stack.pop();
//		 stack.pop();
//		 stack.pop();
//		 stack.pop();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public boolean isValid1(String s) {
		Deque<Character> stack=new LinkedList<>();

		Map<Character,Character>  map = (Map<Character, Character>) Map.of(
				'(', ')',
				'{', '}',
				'[',']',
				'?','?'
		);

		stack.push('?');
		for (Character c : s.toCharArray()) {
			if(map.containsKey(c)){
				stack.push(c);
			} else if( map.get(stack.pop())!=c){
				return false;
			}
		}

		return stack.size()==1;
    }
	//消消樂版本
	public boolean isValid(String s) {

		while (s.contains("{}")||s.contains("[]")|| s.contains("()")){

			if(s.contains("{}")) s=s.replace("{}","");
			if(s.contains("()")) s=s.replace("()","");
			if(s.contains("[]")) s=s.replace("[]","");

		}

		return s.isEmpty();
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
